1499C - Minimum Grid Path - CodeForces Solution

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int maxn=5e5+45,inf=0x3f3f3f3f;
ll idx1,idx2,a[maxn],MIN1[maxn];
ll MIN2[maxn];
ll b[maxn],c[maxn],pre1[maxn],pre2[maxn];
void work(){ 
    int n;
    idx1=idx2=0;
    ll ans=MIN1[0]=MIN2[0]=1e18;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    	scanf("%lld",&c[i]);
//    	MIN[i]=min(MIN[i-1],c[i]);
    	if(i%2)a[++idx1]=c[i];
    	else b[++idx2]=c[i];
	}
	for(int i=1;i<=idx1;i++)pre1[i]=pre1[i-1]+a[i],MIN1[i]=min(MIN1[i-1],a[i]);
	for(int i=1;i<=idx2;i++)pre2[i]=pre2[i-1]+b[i],MIN2[i]=min(MIN2[i-1],b[i]);
	for(int i=2;i<=n;i++){
		int i1,i2;
		if(i%2)i2=i/2,i1=i2+1;
		else i1=i2=i/2;
		ans=min(ans,(n-i1)*MIN1[i1]+pre1[i1]+(n-i2)*MIN2[i2]+pre2[i2]);
//		else ans=min(ans,)
	}
	printf("%lld\n",ans);
}
int main()
{
	int t=1;
	scanf("%d",&t);
	while(t--)
	work();
	return 0;
 }